package ch09_;

public class Ch9_6 {
	private static void permute(StringBuffer sb, int l, int r) {
		if (r == 0) {
			System.out.println(sb.toString());
		} else {
			if (l > 0) {
				StringBuffer s = new StringBuffer(sb);
				permute(s.append("{"), l - 1, r);
			}
			if (r > l) {
				StringBuffer s = new StringBuffer(sb);
				permute(s.append("}"), l, r - 1);
			}
		}
	}
	
	private static void permute(char[] str, int l, int r, int count) {
		if (r == 0) // || count == str.length)
			System.out.println(str);
		else {
			if (l > 0) {
				str[count] = '{';
				permute(str, l - 1, r, count + 1);
			}
			if (r > l) {
				str[count] = '}';
				permute(str, l, r - 1, count + 1);
			}
		}
	}

	public static void permuteSB(int n) {
		if (n <= 0) {
			return;
		}

		StringBuffer sb = new StringBuffer(2 * n);
		permute(sb, n, n);
	}
	
	public static void permuteCA(int n) {
		char[] str = new char[2 * n];
		permute(str, n, n, 0);
	}

	public static void main(String[] args) {
		int n = 15;
		System.out.println("Start!");
		long begin = System.currentTimeMillis();

//		permuteSB(n);
		permuteCA(n);
		System.out.println(System.currentTimeMillis() - begin + " millseconds.");
	}
}
